# !/usr/bin/env python3
# -*- coding: utf-8 -*-
"""
===========================
@Time : 2022/8/21 0021 14:29
@Author : 测试开发工程师
@File : 1. 递归算法.py
@Software: PyCharm
============================
"""

"""
什么是递归？
    递归应用非常广泛，比如 DFS 深度优先搜索，前中后二叉树遍历等
    假设 一群人 在排队，你不清楚自己前面有多少人，可以问前面的人。但你前面也不清楚，整体过程就是递归。
    
    递归公式描述： f(n) = f(n-1) + 1 ,其中 f(1)=1
    int f(int n){
        if (n == 1)return 1;
        return f(n-1) + 1;
        }
    
    什么情况可以使用递归？
        1. 一个问题可以拆分成子问题
        2. 这些问题求解思路相同（数据规模不同）
        3. 拥有终止条件
        
    台阶问题：
    假如 n 个台阶（n >=3 ）,每次可以走1或 2 个台阶，走完 n个台阶有多少种走法？
    比如有3个台阶，可以1，2 或者 2，1
    f(n) = f(n-1)+ f(n-2) 其中：f(1)=1,f(2)=2
    int f(int n){
        if (n == 1) return 1;
        if (n == 2) return 2;
        return f(n-1) + f(n-2);
    }
    
          
    缺点： 重复计算    
    解决方案 ： 把重复计算的内容存起来（使用哈希表）
    
# 哈希表, 把重复计算的内容缓存起来
f(3) = f(1) + f(2)
f(4) = f(3) + f(2) + f(1)

# 有就存，无则取
public int f(int n){
    if (n == 1) return 1;
    if (n == 2) return 2;
    # hasSolvedList 可以理解成一个 Map。key是 n,value 是 f(n)
    if (hasSolvedList.containsKey(n)){
    return hasSolvedList.get(n);
    }
    int ret = f(n-1) + f(n-2);
    hasSolvedList.put(n.ret);
    return ret;
}




内存开销问题： 空间复杂度： O(n)
    int f(int n){
        if (n == 1) return 1;
        return f(n-1) + 1;
    }
    
将递归改写为非递归：
原理： 函数调用底层原理是栈，可以利用 for 循环模拟入栈和出栈操作
    int f(int n){
        int ret =1;
        for (int i = 2;i <= n;i++){
            ret = ret + 1;
        }
        return ret;
    }
    
    int f(int n){
        if (n ==1) return 1;
        if (n ==2) return 2;
        int ret = 0;
        int pre = 2;
        int prepre = 1;
        for (int i = 3;i <= n;++i){
            ret = pre + prepre;
            prepre = pre;
            pre = ret;
            }
        return ret;
        }
    
"""
